Weighted fair queuing algorithms provide data packet scheduling techniques that allow for different scheduling priorities to be assigned to separate data flows (e.g., network traffic streams) over a shared network channel. In weighted fair queuing, each data flow has a separate first-in first out (FIFO) queue. The benefits of weighted fair queuing arise because, as the queues are serviced simultaneously, an “ill-behaved” data flow (i.e., a data flow that has sent either larger packets or more packets per second than other data flows) may be scheduled at a lower priority than other, more “well-behaved” data flows, thus leaving well-behaved data flows generally unaffected.
However, implementations that use weighted fair queuing may, under some circumstances, suffer from performance issues. For example, in typical weighted fair queuing implementations, each FIFO queue is assigned an overall priority, which results in the assignment of the queue priority to all data packets in the queue. If the priority assigned to a FIFO queue is changed, then all data packets in that queue must be updated to reflect the new priority. This entails halting data transmission in all queues, accessing each packet in the queue, updating each packet, and then resuming data transmission. In a server environment that supports multiplexed data communication for time-sensitive applications, the delay resulting from this updating of queue packets may be unacceptable.